#include <vector>
#include <unordered_map>
#include <algorithm>

#include "constants.h"
#include "classes.h"
#include "tools.h"
#include "optimizer_tools.h"
#include "optimizer_center.h"
using namespace std;

OptCenter::OptCenter(AssignInfo &assign_info)
{
    this->assign_info = &assign_info;
    vector<BwType> _tmp(N, LOW);
    this->edge_site_bw_type_vec.reserve(T);
    this->center_site_bw_type_vec.reserve(T);
    for (int t = 0; t < T; ++t)
    {
        this->edge_site_bw_type_vec.push_back(_tmp);
        this->center_site_bw_type_vec.push_back(LOW);
    }
}

double OptCenter::opt(double edge_low_quantile, double edge_hight_quantile, double center_low_quantile, double center_hight_quantile, int min_stream)
{
    this->edge_low_index = ceil(edge_low_quantile * T) - 1;
    this->edge_hight_index = ceil(edge_hight_quantile * T) - 1;
    this->center_low_index = ceil(center_low_quantile * T) - 1;
    this->center_hight_index = ceil(center_hight_quantile * T) - 1;
    this->edge_site_score = 0.0;
    this->center_site_score = 0.0;

    this->min_stream = min_stream;

    this->refresh_state();
    this->total_score = this->edge_site_score + this->center_site_score;

    cout << "total_score:" << (long long)this->total_score
         << " edge_site_score:" << (long long)this->edge_site_score
         << " center_site_score:" << (long long)this->center_site_score
         << endl;

    for (int t = 0; t < T; ++t)
    {
        this->stream_merge_optimize_assign_t(t);
    }
    return this->center_site_score;
}

void OptCenter::refresh_state()
{
    for (int site_id = 0; site_id < N; ++site_id)
    {
        this->refresh_edge_site_state(site_id);
    }
    this->refresh_center_site_state();
}

void OptCenter::refresh_edge_site_state(int site_id)
{
    vector<TAssign *> &assign_vec = this->assign_info->assign_vec;
    int bw_allo_list[T];
    for (int t = 0; t < T; ++t)
    {
        bw_allo_list[t] = assign_vec[t]->site_total_bw[site_id];
    }
    vector<int> bw_sorted_index = arg_sort(bw_allo_list, T, true);

    int target_bw = bw_allo_list[bw_sorted_index[config_info.quantile_index]];
    this->edge_site_score += get_edge_site_score(target_bw, site_info.site_bw_upper[site_id]);

    this->edge_site_low_bw[site_id] = max(bw_allo_list[bw_sorted_index[this->edge_low_index]], config_info.base_cost);
    this->edge_site_high_bw[site_id] = max(bw_allo_list[bw_sorted_index[this->edge_hight_index]], config_info.base_cost);

    for (int i = 0; i < this->edge_low_index; ++i)
    {
        this->edge_site_bw_type_vec[bw_sorted_index[i]][site_id] = LOW;
    }

    for (int i = this->edge_low_index; i <= this->edge_hight_index; ++i)
    {
        this->edge_site_bw_type_vec[bw_sorted_index[i]][site_id] = CRUCIAL;
    }

    for (int i = this->edge_hight_index + 1; i < T; ++i)
    {
        this->edge_site_bw_type_vec[bw_sorted_index[i]][site_id] = BUFFER;
    }

    int _T = T - 1;
    for (int t = 0; t < _T; ++t)
    {
        if ((this->edge_site_bw_type_vec[t][site_id] == BUFFER) && (this->edge_site_bw_type_vec[t + 1][site_id] == BUFFER))
        {
            this->edge_site_bw_type_vec[t][site_id] = RADICAL;
        }
    }
    if (this->edge_site_bw_type_vec[_T][site_id] == BUFFER)
    {
        this->edge_site_bw_type_vec[_T][site_id] = RADICAL;
    }
}

void OptCenter::refresh_center_site_state()
{
    vector<TAssign *> &assign_vec = this->assign_info->assign_vec;
    long long bw_allo_list[T];
    for (int t = 0; t < T; ++t)
    {
        bw_allo_list[t] = assign_vec[t]->center_site_bw;
    }
    vector<int> bw_sorted_index = arg_sort(bw_allo_list, T, true);

    long long target_bw = bw_allo_list[bw_sorted_index[config_info.quantile_index]];
    this->center_site_score = get_center_site_score(target_bw);

    this->center_site_low_bw = bw_allo_list[bw_sorted_index[this->center_low_index]];
    this->center_site_high_bw = bw_allo_list[bw_sorted_index[this->center_hight_index]];

    for (int i = 0; i < this->center_low_index; ++i)
    {
        this->center_site_bw_type_vec[bw_sorted_index[i]] = LOW;
    }

    for (int i = this->center_low_index; i <= this->center_hight_index; ++i)
    {
        this->center_site_bw_type_vec[bw_sorted_index[i]] = CRUCIAL;
    }

    for (int i = this->center_hight_index + 1; i < T; ++i)
    {
        this->center_site_bw_type_vec[bw_sorted_index[i]] = RADICAL;
    }
}

void OptCenter::stream_merge_optimize_assign_t(int t)
{
    TAssign *tassign = this->assign_info->assign_vec[t];
    tassign->refresh_inherited_bw();
    tassign->refresh_total_bw();
    process_overflow_t(tassign);

    const BwType &t_center_site_bw_type = this->center_site_bw_type_vec[t];

    if (t_center_site_bw_type == CRUCIAL)
    {
        this->stream_merge_crucial_center(t, tassign);
    }
}

void OptCenter::stream_merge_crucial_center(int t, TAssign *tassign)
{
    //从大到小遍历当前时刻的3500个流
    vector<int> safe_bw_uppers = this->get_safe_bw_uppers(t, tassign);

    //流整合
    for (auto &demand_bw_node : tassign->tdemand->sorted_deamnd_bw) //已经是按照带宽需求从大到小排序的
    {

        const int &demand_bw = demand_bw_node.bandwidth;

        // 为0的流不作处理
        if (!demand_bw)
        {
            continue;
        }

        const int &client_id = demand_bw_node.client_id;
        const int &stream_id = demand_bw_node.stream_id;

        const int &from_site_id = tassign->stream_client_to_allo_node[stream_id][client_id].site_id;            // 这个流来自哪
        int selected_site_id = -1;                                                                              // 用来指向成本最低的流
        int max_decrease_score = -1;                                                                            // 用来标记减少最多的量
        int min_gap_score = 1000000;                                                                            // 用来标记与上一最大值差距最小的量
        int max_left_allo_bw = safe_bw_uppers[from_site_id] - tassign->site_total_bw[from_site_id] - demand_bw; // 用来标记剩余能分配最多的量
        bool is_select_left_max_site = false;
        // 当有多个满足的分配方案时，选择gap小的分配。比如 50 这个流 能分给 最大值为100 和 200的，50->100的gap为50；50->200的gap为150；

        for (auto &to_site_id : client_info.client_to_sites[client_id])
        {
            if (from_site_id == to_site_id)
            {
                continue; // 自己就没必要再分给自己了
            }

            if (demand_bw < this->min_stream)
            {
                continue; // 太小流没必要处理，浪费时间
            }

            if ((tassign->site_total_bw[to_site_id] + demand_bw) > safe_bw_uppers[to_site_id])
            {
                continue; // 分配流量后会超出安全上界，跳过
            }

            int gap_score = INT32_MAX;
            int decrease_score = INT32_MAX;
            int left_allo_bw = INT32_MIN;

            //判断该流是否可以分配给该节点，不会导致中心节点增大就可以分配
            if (this->check_is_score_decrease(from_site_id, to_site_id, stream_id, client_id, demand_bw, tassign, gap_score, decrease_score, left_allo_bw))
            {
                // 选择降低中心节点带宽最多的节点
                if (decrease_score > max_decrease_score)
                {
                    max_decrease_score = decrease_score;
                    selected_site_id = to_site_id;
                    is_select_left_max_site = false;
                }
                // 如果中心节点带宽降低的一样多，这里通常是都为0的情况，看那个会使得gap_score更小，选哪个
                else if (decrease_score == max_decrease_score)
                {
                    if (gap_score < min_gap_score)
                    {
                        min_gap_score = gap_score;
                        selected_site_id = to_site_id;
                        is_select_left_max_site = false;
                    }
                    // 如果大家降低的都是0，并且都没有gap_score，
                    // 也就是说从from_site分配出去的流是from_site的最大流，
                    // 接受到的site_id接受也是最大流。这个时候，
                    // 我们选择剩余可分配量（safe_upper-total_bw）最大的结点
                    else if (min_gap_score == 1000000) // min_gap_score = 1000000表示目前为止分出去的都没有gap_score，也就是都是上述情况
                    {
                        //记录一个升序可分配量最大的结点
                        left_allo_bw = safe_bw_uppers[to_site_id] - tassign->site_total_bw[to_site_id] - demand_bw;
                        if (left_allo_bw > max_left_allo_bw)
                        {
                            max_left_allo_bw = left_allo_bw;
                            selected_site_id = to_site_id;
                            is_select_left_max_site = true;
                        }
                    }
                }
            }
        }

        if (selected_site_id != -1)
        {
            tassign->transfer(stream_id, client_id, selected_site_id);
            if (is_select_left_max_site)
            {
                get_stream_bw_from_connect_client(t, tassign, safe_bw_uppers, selected_site_id, stream_id);
            }
        }
    }
}

bool OptCenter::check_is_score_decrease(int from_site_id, int to_site_id, int stream_id, int client_id, int bandwidth, TAssign *tAssign,
                                        int &to_gap_score, int &decrease_score, int &left_allo_bw)
{
    SiteAlloInfo &to_site_allo_info = tAssign->site_stream_to_allo_info[to_site_id][stream_id];
    SiteAlloInfo &from_site_allo_info = tAssign->site_stream_to_allo_info[from_site_id][stream_id];
    int to_site_increase_cost = INT32_MAX;
    int from_site_decrease_cost = INT32_MIN;

    //目标节点该流下没有带宽，那中心增长就是带宽值
    if (!to_site_allo_info.count)
    {
        to_site_increase_cost = bandwidth;
    }
    else
    {
        // 目标节点该流下有带宽，并且带宽最大值大于待分配值，那中心增长就是0，这个时候需要求gap_score，找出比待分配大的值
        if (to_site_allo_info.largest_bw >= bandwidth)
        {
            // from_site的gap_score
            int from_gap_score = INT32_MAX;

            AlloNode &from_allo_node = tAssign->stream_client_to_allo_node[stream_id][client_id];

            // from_site上该流下只有一个带宽，所以这个带宽的gap_score是最大值
            if (from_allo_node.pre_site_allo)
            {
                from_gap_score = from_allo_node.pre_site_allo->bandwidth - bandwidth;
            }

            //目标site的gap_score
            to_site_increase_cost = 0;
            AlloNode *to_allo_node = to_site_allo_info.head;
            if (to_site_allo_info.count == 1)
            {
                to_gap_score = to_allo_node->bandwidth - bandwidth;
            }
            else
            {
                while (to_allo_node->next_site_allo != to_site_allo_info.tail)
                {
                    if (to_allo_node->next_site_allo->bandwidth < bandwidth)
                    {
                        break;
                    }
                    else
                    {
                        to_allo_node = to_allo_node->next_site_allo;
                    }
                }
                if (to_allo_node->next_site_allo->bandwidth < bandwidth)
                {
                    to_gap_score = to_allo_node->bandwidth - bandwidth;
                }
                else
                {
                    to_gap_score = to_allo_node->next_site_allo->bandwidth - bandwidth;
                }
            }
            // 如果移动后的gap_score 比 当前的gap_score小，那就可以，否则，移动后的gap_score置为最大值
            if (to_gap_score >= from_gap_score)
            {
                to_gap_score = INT32_MAX;
            }
        }
        // 目标节点该流下有带宽，并且该流下的最大值小于待分配值，那中心增长就是待分配减去最大值
        else
        {
            to_site_increase_cost = bandwidth - to_site_allo_info.largest_bw;
        }
    }

    //  from_site节点只有当前一个流，减少的价值就是bandwidth
    if (from_site_allo_info.count == 1)
    {
        from_site_decrease_cost = bandwidth;
    }
    else
    {
        //说明要转移的节点可能是最大的，也可能是次大的，只要不是最大，转移成本就不会降低。
        if (from_site_allo_info.largest_bw == bandwidth)
        {
            //说明当前要转移的是最大的，那就计算转移降低的量是多少
            from_site_decrease_cost = bandwidth - from_site_allo_info.head->next_site_allo->bandwidth;
        }
        else
        {
            //说明要转移的是次大的，那就降低量为0
            from_site_decrease_cost = 0;
        }
    }

    // 如果减少量大于增加量，那说明此次转移 会降低中心节点，那就返回ture
    if (from_site_decrease_cost >= to_site_increase_cost)
    {
        decrease_score = from_site_decrease_cost - to_site_increase_cost;
        return true;
    }

    return false;
}

void OptCenter::get_stream_bw_from_connect_client(int t, TAssign *tAssign, vector<int> &safe_bw_uppers, int target_site_id, int target_steam_id)
{
    bool should_ask[MAX_M] = {0};
    for (auto &client_id : site_info.site_to_clients[target_site_id])
    {
        // 只有那些没分给target_id的结点，才需要询问是否可以拿过来
        if (tAssign->stream_client_to_allo_node[target_steam_id][client_id].site_id != target_site_id)
        {
            should_ask[client_id] = true;
        }
    }
    while (tAssign->site_total_bw[target_site_id] <= safe_bw_uppers[target_site_id])
    {
        int selected_site_id = -1;
        int selected_client_id = -1;
        int max_decrease_score = -1; // 用来标记减少最多的量
        //当有多个满足的分配方案时，选择gap小的分配。比如 50 这个流 能分给 最大值为100 和 200的，50->100的gap为50；50->200的gap为150；
        int min_gap_score = 1000000; //用来标记与上一最大值差距最小的量
        int max_left_allo_bw = -1;   //用来标记剩余能分配最多的量

        for (auto client_id : site_info.site_to_clients[target_site_id])
        {
            if (!should_ask[client_id])
            {
                continue;
            }

            const int &stream_id = target_steam_id;
            const int &demand_bw = tAssign->tdemand->demand_bw_matrix[stream_id][client_id];
            const int &from_site_id = tAssign->stream_client_to_allo_node[stream_id][client_id].site_id;

            //如果加上这个带宽会使得超过safe_bw，那么就不再考虑这个结点
            if ((tAssign->site_total_bw[target_site_id] + demand_bw) > safe_bw_uppers[target_site_id])
            {
                should_ask[client_id] = 0;
                continue;
            }
            if (from_site_id == -1)
            {
                should_ask[client_id] = 0;
                continue;
            }
            int decrease_score = INT32_MAX;
            int gap_score = INT32_MAX;
            int left_allo_bw = INT32_MIN;
            if (this->check_is_score_decrease(from_site_id, target_site_id, stream_id, client_id, demand_bw, tAssign,
                                              gap_score, decrease_score, left_allo_bw))
            {
                if (decrease_score > max_decrease_score)
                {
                    max_decrease_score = decrease_score;
                    selected_site_id = from_site_id;
                    selected_client_id = client_id;
                }
                // 如果中心节点带宽降低的一样多，这里通常是都为0的情况，看那个会使得gap_score更小，选哪个
                else if (decrease_score == max_decrease_score)
                {
                    if (gap_score < min_gap_score)
                    {
                        min_gap_score = gap_score;
                        selected_site_id = from_site_id;
                        selected_client_id = client_id;
                    }
                    // 如果大家降低的都是0，并且都没有gap_score，
                    // 也就是说从from_site分配出去的流是from_site的最大流，
                    // 接受到的site_id接受也是最大流。这个时候，
                    // 我们选择剩余可分配量（safe_upper-total_bw）最大的结点
                    else if (min_gap_score == 1000000) // min_gap_score = 1000000表示目前为止分出去的都没有gap_score，也就是都是上述情况
                    {
                        //记录一个升序可分配量最大的结点
                        left_allo_bw = safe_bw_uppers[from_site_id] - tAssign->site_total_bw[from_site_id] - demand_bw;
                        if (left_allo_bw > max_left_allo_bw)
                        {
                            max_left_allo_bw = left_allo_bw;
                            selected_site_id = from_site_id;
                            selected_client_id = client_id;
                        }
                    }
                }
            }
            else
            {
                should_ask[client_id] = 0;
            }
        }
        if (selected_site_id != -1)
        {
            tAssign->transfer(target_steam_id, selected_client_id, target_site_id);
            should_ask[selected_client_id] = 0;
        }
        else
        {
            return;
        }
    }
}

vector<int> OptCenter::get_safe_bw_uppers(int t, TAssign *tassign)
{
    vector<int> bw_upper(N, 0);
    vector<BwType> &edge_site_bw_types = this->edge_site_bw_type_vec[t];
    for (int site_id = 0; site_id < N; site_id++)
    {
        const int &low_bw = this->edge_site_low_bw[site_id];
        int &_upper = bw_upper[site_id];
        const BwType &bw_type = edge_site_bw_types[site_id];
        switch (bw_type)
        {
        case LOW:
            _upper = low_bw;
            break;
        case CRUCIAL:
            _upper = max(tassign->site_total_bw[site_id], config_info.base_cost);
            break;
        case BUFFER: // BUFFER一定不会出现在最后一个时刻
        {
            _upper = (low_bw - tassign->next_tassign->site_allocated_bw[site_id]) / INHERIT_RATE;
            _upper = max(_upper, tassign->site_total_bw[site_id]);
            break;
        }
        case RADICAL:
        {
            if (tassign->next_tassign)
            {
                _upper = (site_info.site_bw_upper[site_id] - tassign->next_tassign->site_allocated_bw[site_id]) / INHERIT_RATE;
                _upper = max(_upper, tassign->site_total_bw[site_id]);
            }
            else
            {
                _upper = site_info.site_bw_upper[site_id];
            }
            break;
        }
        }
        _upper = min(_upper, site_info.site_bw_upper[site_id]);
    }
    return bw_upper;
}